class Solution {
public:
    vector<vector<int>> ret;
    vector<int> tmp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        dfs(candidates, target, 0, 0);
        return ret;
    }

    void dfs(vector<int>& candidates, int target, int curSum, int cur)
    {
        if (curSum == target)
        {
            ret.push_back(tmp);
            return;
        }
        else if (curSum > target)return;

        tmp.push_back(candidates[cur]);
        dfs(candidates, target, curSum + candidates[cur], cur);
        tmp.pop_back();

        if (cur + 1 < candidates.size())
            dfs(candidates, target, curSum, cur + 1);
    }
};